package com.lisp.algorithm.sort;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        // {5, 3, 8, 2, 4, 5, 9, 20, 11, 2, 13}
        int nums[] = {5, 3, 8, 2, 4, 5, 9, 20, 11, 2, 13};
        sort(nums, 0, nums.length);
        System.out.println(Arrays.toString(nums));
    }
    
    private static void sort(int a[], int start, int end) {
        // System.out.println(String.format("start sort start=%s, end=%s", start, end));
        int n = end - start;
        if(n > 1) {
            int middle = n/2;
            sort(a, start, start+middle);
            sort(a, start+middle, start+n);
            merge(a, start, start+middle, end);
        }
        // System.out.println(String.format("after sort a=%s", Arrays.toString(a)));
    }
    
    private static void merge(int a[], int p, int q, int r) {
        System.out.println(String.format("start merge p=%s, q=%s, r=%s", p, q, r));
        for(int i=q; i<r; i++) {
            for(int j=i; j>p; j--) {
                if(a[j-1] > a[j]) {
                    int tmp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = tmp;
                }
            }
        }
        System.out.println(String.format("after merge a=%s", Arrays.toString(a)));
    }
}
